Dada una gramática libre de contexto G=(Σ,N,P,S) y una frase de entrada w ∈ Σ^*, un Analizador Sintáctico Descendente (Top-Down Parser) intenta encontrar una derivación izquierda de la frase partiendo del símbolo no-terminal inicial S y reemplazando el no-terminal más a la izquierda por el lado derecho de una producción que tenga a ese no-terminal por lado izquierdo.

Configuración

Una configuración es una tupla que describe el estado de una máquina o procedimiento de análisis sintáctico en un momento dado. En el caso del Analisis Sintactico Descendente, dada una gramática G=(Σ,N,P,S), una configuración es una tupla:

⟨w$, Xα$, Π⟩

donde:

w ∈ Σ^*
Xα ∈ (Σ ∪ N)*, S ⇒^* a
Π=p ₁ p ₂ ... p _n | p _i∈ P

Y donde w es la parte de la cadena de entrada que queda por consumir, Xa es una forma sentencial obtenida mediante una derivación izquierda, y X es el símbolo más a la izquierda en dicha sentencia, y Π es la secuencia de producciones que produjeron dicha derivación. El símbolo $ es un nuevo símbolo que no está en S ni en N, y que usamos para denotar tanto el final de la secuencia de entrada como el de la forma sentencial.

Movimientos o Cómputos

Un movimiento (o cómputo) en una derivación es el paso de una configuración a otra, y se indica por el símbolo ├─. Los símbolos ├─ ^*, ├─ ⁺, y ├─ ^k tienen los significados usuales.

Derivaciones y Configuraciones

Con las configuraciones podemos describir de manera conveniente un proceso de derivación:

1. Si el símbolo más a la izquierda de la forma sentencial es un no-terminal, el mismo se substituye por la parte derecha de una de las producciones.
2. Si el símbolo más a la izquierda en la forma sentencial es un no-terminal distinto al primer símbolo en la entrada, se retrocede hasta la última sustitución de un no-terminal y se selecciona una producción distinta para hacer la sustitución. Si no hay más producciones que elegir, se aplica otro retroceso. Si es posible retroceder, la frase de entrada no pertenece al lenguaje
3. Cada vez que en una configuración el primer símbolo de la entrada coincide con el primer símbolo en la forma sentencial derivada hasta el momento, ambos símbolos se consumen.

Ejemplo

Dada la gramática

1. S → ( L )
2. L → A L
3. L → A
4. A → S
5. A → a

Hecho eso, podemos usar configuraciones para describir el proceso de análisis descendente de la frase de entrada: ((a)(a)a).

⟨((a)(a)a)$,S$,⟩	sustituir 1
├─⟨((a)(a)a)$,(L)$,1⟩	consumir (
├─⟨(a)(a)a)$,L)$,1⟩	sustituir 2
├─⟨(a)(a)a)$,AL)$,1 2⟩	sustituir 4
├─⟨(a)(a)a)$,SL)$,1 2 4⟩	sustituir 1
├─⟨(a)(a)a)$,(L)L)$,1 2 4 1⟩	consumir (
├─⟨a)(a)a)$,L)L)$,1 2 4 1⟩	sustituir 3
├─⟨a)(a)a)$,A)L)$,1 2 4 1 3⟩	sustituir 5
├─⟨a)(a)a)$,a)L)$,1 2 4 1 3 5⟩	consumir a
├─⟨)(a)a)$,)L)$,1 2 4 1 3 5⟩	consumir (
├─⟨(a)a)$,L)$,1 2 4 1 3 5⟩	sustituir 2
├─⟨(a)a)$,AL)$,1 2 4 1 3 5 2⟩	sustituir 4
├─⟨(a)a)$,SL)$,1 2 4 1 3 5 2 4⟩	sustituir 1
├─⟨(a)a)$,(L)L)$,1 2 4 1 3 5 2 4 1⟩	consumir (
├─⟨a)a)$,L)L)$,1 2 4 1 3 5 2 4 1⟩	sustituir 3
├─⟨a)a)$,A)L)$,1 2 4 1 3 5 2 4 1 3⟩	sustituir 5
├─⟨a)a)$,a)L)$,1 2 4 1 3 5 2 4 1 3 5⟩	consumir a
├─⟨)a)$,)L)$,1 2 4 1 3 5 2 4 1 3 5⟩	consumir )
├─⟨a)$,L)$,1 2 4 1 3 5 2 4 1 3 5⟩	sustituir 3
├─⟨a)$,A)$,1 2 4 1 3 5 2 4 1 3 5 3⟩	sustituir 4
├─⟨a)$,S)$,1 2 4 1 3 5 2 4 1 3 5 3 4⟩	sustituir 1
⟨a)$,(L)$,1 2 4 1 3 5 2 4 1 3 5 3 4 1⟩	retroceder 1
⟨a)$,S$,1 2 4 1 3 5 2 4 1 3 5 3 4⟩	retroceder 4
├─⟨a)$,A)$,1 2 4 1 3 5 2 4 1 3 5 3⟩	sustituir 5
├─⟨a)$,a)$,1 2 4 1 3 5 2 4 1 3 5 3 5⟩	consumir a
├─⟨)$,)$,1 2 4 1 3 5 2 4 1 3 5 3 5⟩	consumir )
├─⟨$,$,1 2 4 1 3 5 2 4 1 3 5 3 5⟩	fin

Como la derivación anterior demuestra, el análisis sintáctico descendente recursivo con retroceso (ASDRR) puede ser un proceso costoso incluso para gramáticas y frases de entrada sencillas. En particular, un ASDRR puede realizar una cantidad enorme de trabajo antes de darse cuenta que la decisión tomada en uno de los pasos iniciales fue equivocada.